geompack Module

public subroutine alpha_measure(n, z, triangle_order, triangle_num, triangle_node, alpha_min, alpha_ave, alpha_area)

Determines the triangulated pointset quality measure ALPHA.

The ALPHA measure evaluates the uniformity of the shapes of the triangles defined by a triangulated pointset.

We compute the minimum angle among all the triangles in the triangulated dataset and divide by the maximum possible value (which, in degrees, is 60). The best possible value is 1, and the worst 0. A good triangulation should have an ALPHA score close to 1.

The code has been modified to 'allow' 6-node triangulations. However, no effort is made to actually process the midside nodes. Only information from the vertices is used.

Arguments

public function angle_rad_2d(p1, p2, p3) result(rst)

Returns the angle swept out between two rays in 2D.

Arguments

Return Value real(kind=real64)

The angle swept out by the rays, in radians. If either ray has zero length, then the angle is set to 0.

public function diaedg(x0, y0, x1, y1, x2, y2, x3, y3) result(rst)

Chooses a diagonal edge.

The routine determines whether 0--2 or 1--3 is the diagonal edge that should be chosen, based on the circumcircle criterion, where (X0,Y0), (X1,Y1), (X2,Y2), (X3,Y3) are the vertices of a simple quadrilateral in counterclockwise order.

Arguments

Return Value integer(kind=int32)

The edge.

public function lrline(xu, yu, xv1, yv1, xv2, yv2, dv) result(rst)

Determines if a point is left of, right of, or on a directed line.

The directed line is parallel to, and at a signed distance DV from a directed base line from (XV1,YV1) to (XV2,YV2).

Arguments

Return Value integer(kind=int32)

+1, the point is to the right of the directed line; 0, the point is on the directed line; -1, the point is to the left of the directed line.

public subroutine perm_check(n, p, ierror)

Checks that a vector represents a permutation.

The routine verifies that each of the values from 1 to N occurs among the N entries of the permutation.

Arguments

public subroutine perm_inverse(n, p)

Inverts a permutation in-place.

Arguments

public subroutine points_delaunay_naive_2d(node_num, node_xy, maxtri, triangle_num, triangle_node)

A naive Delaunay triangulation scheme.

This routine is only suitable as a demonstration code for small problems. Its running time is of order NODE_NUM**4. Much faster algorithms are available.

Given a set of nodes in the plane, a triangulation is set of triples of distinct nodes, forming triangles, so that every point within the convex hull of the set of nodes is either one of the nodes, or lies on an edge of one or more triangles, or lies within exactly one triangle.

A Delaunay triangulation is a triangulation with additional properties.

NODE_NUM must be at least 3.

Arguments

public subroutine points_hull_2d(node_num, node_xy, hull_num, hull)

Computes the convex hull of 2D points.

The work involved is N*log(H), where N is the number of points, and H is the number of points that are on the hull.

Arguments

public subroutine quad_convex_random(seed, xy)

Returns a random convex quadrilateral.

The quadrilateral is constrained in that the vertices must all lie with the unit square.

Arguments

public subroutine r8tris2(node_num, node_xy, triangle_num, triangle_node, triangle_neighbor)

Constructs a Delaunay triangulation of 2D vertices.

The routine constructs the Delaunay triangulation of a set of 2D vertices using an incremental approach and diagonal edge swaps. Vertices are first sorted in lexicographically increasing (X,Y) order, and then are inserted one at a time from outside the convex hull.

Arguments

public subroutine triangle_circumcenter_2d(t, center)

Computes the circumcenter of a triangle in 2D.

The circumcenter of a triangle is the center of the circumcircle, the circle that passes through the three vertices of the triangle.

The circumcircle contains the triangle, but it is not necessarily the smallest triangle to do so.

If all angles of the triangle are no greater than 90 degrees, then the center of the circumscribed circle will lie inside the triangle. Otherwise, the center will lie outside the circle.

The circumcenter is the intersection of the perpendicular bisectors of the sides of the triangle.

In geometry, the circumcenter of a triangle is often symbolized by "O".

Arguments